package 动态规划;

/**
 * ---------------------------------------------------------
 * <h></h>
 * <p>
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *  
 * 示例 1：
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 * <p>
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 * <p>
 * 输入：s = "ac"
 * 输出："a"
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母（大写和/或小写）组成
 * <p>
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * </p>
 * Created by Frank on 2021/4/7.
 * <a href="mailto:frankyao10110@gmail.com">Contact me</a>
 * ---------------------------------------------------------
 */
public class _最长回文子串 {
    public static void main(String[] args) {
        String p = longestPalindrome("cbbd");
        System.out.println("palindrome=" + p);
    }

    /**
     * 中心拓展优化，以字符相同的串为中心
     * <p>
     * 'a', 'bbb', 'aa' etc.
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        char[] cs = s.toCharArray();

        int begin = 0;
        int length = 1;
        //以字符相同的串为中心，向两边拓展，如果l != r，则另 i = r，可以减少无效查找的次数。
        for (int i = 0; i < cs.length; i++) {
            System.out.println("i=" + i);

            int l = i - 1;
            int r = i + 1;

            while (r < cs.length && cs[i] == cs[r]) {
                r++;
            }

            int oldR = r;

            while (l >= 0 && r < cs.length && cs[l] == cs[r]) {
                l--;
                r++;
            }

            System.out.println("l=" + l);
            System.out.println("r=" + r);
            int curLen = r - l - 1;
            System.out.println("curLen=" + curLen);

            if (curLen > length) {
                length = curLen;
                l++;
                begin = l;
            }
            System.out.println("oldR=" + oldR);

            i = oldR - 1;
        }

        System.out.println("begin=" + begin);
        System.out.println("length=" + length);

        return new String(cs, begin, length);
    }

    public static String longestPalindrome2(String s) {
        if (s == null || s.length() < 2) return s;
        char[] cs = s.toCharArray();

        int begin = 0;
        int length = 1;

        //假设dp数组记录是否是回文串，dp[i][j]代表cs[i,j]的字符串是否为回文串
        boolean[][] dp = new boolean[cs.length][cs.length];

        //dp[i][j]需要通过dp[i-1][j-1]来判断，s[i-1][j-1]是左下角的值
        //且应该从短到长来判断，s[8,j],s[7,j]..s[0,j],故i应该从大到小遍历
        //cs[i,j]有效的范围i <= j
        for (int i = cs.length - 1; i >= 0; i--) {
            for (int j = i; j < cs.length; j++) {
                //对于一个cs[i,j]字符串，如果子串是回文串且第一个字符等于最后一个字符，则cs字符串是回文串
                int len = j - i + 1;
                dp[i][j] = (cs[i] == cs[j]) && (len <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j] && length <= len) {
                    length = len;
                    begin = i;
                }
            }
        }

        System.out.println("begin=" + begin);
        System.out.println("length=" + length);
        return new String(cs, begin, length);

    }
}
